package basic.study.wantOffer.chapter3;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;

/**
 * @author Kevin
 * @date 2020/5/11 14:13
 * 字符串的排序
 * 注意，求的是排列，范围是比组合要大的，考虑次序，所以用交换
 * 排列：对于每一个数字，考虑和之后的字符串每一个数字交换不交换
 * 组合：对于每一个数字，考虑再组合中存在不存在
 * https://www.nowcoder.com/questionTerminal/fe6b651b66ae47d7acce78ffdd9a96c7?f=discussion
 */
public class Problem38 {
    //第一种算法，递归
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> list = new ArrayList<String>();
        if (str != null && str.length() > 0) {
            PermutationHelper(str.toCharArray(), 0, list);
            Collections.sort(list);
        }
        return list;
    }

    /**
     * 回溯
     * @param chars
     * @param i
     * @param list
     */
    private void PermutationHelper(char[] chars, int i, ArrayList<String> list) {
        if (i == chars.length -1) {
            list.add(String.valueOf(chars));
        } else {
            HashSet<Character> set = new HashSet<Character>();
            for (int j = i; j < chars.length; j++) {
                //set去重
                if(j == i || !set.contains(chars[j])) {
                    set.add(chars[j]);
                    swap(chars, i, j);
                    PermutationHelper(chars, i+1, list);
                    //回溯
                    swap(chars, j, i);
                }
            }
        }
    }
    private void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }

}
